/*
	Copyright (c) 2009-2011, Stefan Webb.

	This file is part of SimpleML. Please read the file "license.txt", 
	which contains the conditions under which this software is distributed.
*/

/*!
	\file patriciatree.cpp
	\author Stefan Webb
	\brief Definition of PatriciaTree class.
*/

#ifndef PATRICIATREE_H
#define PATRICIATREE_H

/*! \brief Initial size of bucket for default constructor. */
#define INITIAL_PTREE_SIZE 16

// Don't forget that on 64-bit architectures, pointer size will double
// Do I want to fix the pointer size to 32-bits on all architectures?
/*! \brief Structure for internal tree node. */
struct PatriciaNode
{
	/*! \brief Index of left and right children (x 2 to free up first bit). */
	unsigned int child[2];

	/*! \brief Index of byte that differs. Fourth byte contains bitMask */
	unsigned int indexByte;

	/*! \brief Bit mask used to show bit that differs. */
	//unsigned short int bitMask;
};

/*! \brief Mask for bits indicating which bit differs. */
#define BITMASK 0xff000000

/*! \brief Mask for bits indicating which byte differs. */
#define INDEXMASK 0x00ffffff

/*!	\brief Efficient data structure for searching a set of strings. */
class PatriciaTree : protected ContainsNodes<PatriciaNode>
{
public:
	/*! \brief Default constructor. */
	PatriciaTree();

	/*! \brief Constructor with initial memory size.
		\param size Initial number of nodes for which to allocate memory. */
	PatriciaTree(unsigned int size);

	/*! \brief Default destructor. */
	~PatriciaTree();

	/*! \brief Test membership of patricia tree.
		\param string String of which to test membership.
		\return True if patricia tree contains string (and cursor is updated).
		False otherwise. */
	bool contains(const utf16* string);

	/*! \brief Insert string into patricia tree. No handover of memory ownership.
		\param string String for insertion. */
	bool insert(const utf16* string);

	/*! \brief Remove string from patricia tree.
		\param string String for removal. */
	bool remove(const utf16* string);

	/*! \brief Remove string at current cursor position. Update cursor. */
	void remove();

	/*! \brief Empty entire patricia tree. */
	void empty();

	/*! \brief Get first string in patricia tree.
		\return First string in patricia tree. Update cursor. */
	utf16* first();

	/*! \brief Get last string in patricia tree.
		\return Last string in patricia tree. Update cursor. */
	utf16* last();

	/*! \brief Get string at current cursor position.
		\return String at current cursor position. */
	utf16* cursor();

	/*! \brief Get next string in patricia tree. Update cursor.
		\return Next string in patricia tree. Zero if none. */
	utf16* successor();

	/*! \brief Get previous string in patricia tree. Update cursor.
		\return Previous string in patricia tree. Zero if none. */
	utf16* predecessor();

	/* Debug function */
	void print();

	/* Debug function */
	void printNodes();

protected:
	/*! \brief Given a string, will find best match in patricia tree.
		\param string String to find best match for.
		\return Best match for string. */
	utf16* bestMatch(const utf16* string);

	/*! \brief Calculate the index byte for a given node.
		\param i Node for which to calculate index byte.
		\return Index byte for specified node. */
	unsigned int indexByte(unsigned int i);

	/*! \brief Calculate the bit mask for a given node.
		\param i Node for which to calculate the bit mask.
		\return Bit mask for specified node. */
	unsigned int bitMask(unsigned int i);

	/*! \brief Allocates memory for cursor. Cursor only created when needed. */
	void createCursor();

	/*! \brief Follows either left or right branches until leaf, adding each node to cursor.
		\param direction Direction to follow. 0 for left, 1 for right.
		\return String at leaf. */
	utf16* followBranch(unsigned int direction);

	/*! \brief Helper function that gets adjacent element and updates cursor. 
		\param direction 0 for adjacent element on left, 1 for on right.
		\return String for adjacent element. */
	utf16* adjacent(unsigned int direction);

	/*! \brief Cursor stack. */
	Stack<unsigned int> cursor_;
};

#endif